package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * b
 * back
 * 77. 组合
 * 剑指 Offer II 080. 含有 k 个元素的组合
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/13 17:01
 */
public class Combine {

    public static void main(String[] args) {
        Combine test = new Combine();
        int n = 4;
        int k = 2;
        List<List<Integer>> combine = test.combine(n, k);
        System.out.println(combine);
    }

    private int n;
    private int k;
    private List<List<Integer>> all = new ArrayList<>();
    private List<Integer> list = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        if (k > n) {
            return all;
        }
        this.k = k;
        this.n = n + 1;
        for (int i = 1; i <= n; i++) {
            list.add(i);
            find(i + 1);
            list.remove(0);
        }
        return all;
    }

    private void find(int index) {
        if (index > n || list.size() + n - index + 1 < k) {
            return;
        }
        if (list.size() == k) {
            all.add(new ArrayList<>(list));
            return;
        }
        find(index + 1);
        list.add(index);
        find(index + 1);
        list.remove(list.size() - 1);
    }


    // 官方
    public List<List<Integer>> combine2(int n, int k) {
        List<List<Integer>> lists = new ArrayList<>();
        //如果k>n，数据都不够，直接返回吧..
        if (k > n) {
            return lists;
        }
        dfs(1, n, lists, new ArrayList<>(), k);
        return lists;
    }

    private void dfs(int index, int n, List<List<Integer>> lists, List<Integer> list, int k) {
        //当剩余需要添加的数的个数是0的时候，已经满足数据个数了，保存并结束方法
        if (k == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }
        //当index>n时，已经超出n的范围了，结束...
        if (index > n) {
            return;
        }
        for (int i = index; i <= n - k + 1; i++) {
            list.add(i);
            dfs(i + 1, n, lists, list, k - 1);
            list.remove(list.size() - 1);
        }
    }

}
